package item03;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author Lv Jing
 * @date 2018年07月10日 1:26
 */
public class Arr01 {

    /*
    题目一：找出数组中重复的数字，数组长度为n，数字范围在0~n-1里
    通过数组角标与数组的值构成哈希表，比如角标为i的数如果不等于i，则判断当前角标i的值，以它为角标的值与当前角标i的值比较，
    如果不相等则进行交换，相等证明两个角标处的值相等即为重复数；如果等于，则可切换到下一个数。
     */

    private int getDuplication(int[] arr) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        for (int value : arr) {
            if (value < 0 || value > arr.length-1) {
                return -1;
            }
        }

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == i) {
                continue;
            }
            while (arr[i] != i) {
                if (arr[arr[i]] != arr[i]) {
                    int temp = arr[arr[i]];
                    arr[arr[i]] = arr[i];
                    arr[i] = temp;
                } else {
                    return arr[i];
                }
            }
        }
        return -1;
    }

    /**
     * 输入null
     */
    @Test
    public void test01() {
        Assert.assertEquals(getDuplication(null), -1);
    }

    /**
     * 数组不符合题目要求
     */
    @Test
    public void test02() {
        int[] arr = {-1, 2, 2, 3};
        Assert.assertEquals(getDuplication(arr), -1);
    }

    /**
     * 正常情况
     */
    @Test
    public void test03() {
        int[] arr = {2, 3, 5, 4, 3, 2, 6, 7};
        Assert.assertEquals(getDuplication(arr), 2);
    }
}
